<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <!-- 
        解题思路：
        - 新链表的下一个节点一定是K个链表头中最小节点
        - 考虑选择使用最小堆

        解题步骤：
        - 构建一个最小堆，并依次把链表头插入堆中
        - 弹出堆顶接到输出链表，并将堆顶所在链表的新链表头插入堆中
        - 等堆元素全部弹出，合并工作就完成了
     -->
</head>
<body>
    <script>
        class MinHeap {
            constructor() {
                this.heap = [];
            }
            // 交换两个节点
            swap(i1, i2) {
                const temp = this.heap[i1];
                this.heap[i1] = this.heap[i2];
                this.heap[i2] = temp;
            }
            // 获取父节点
            getParentIndex(i) {
                return (i - 1) >> 1; // 相当于 Math.floor((i-1) / 2);
            }
            // 获取左子节点
            getLeftIndex(i) {
                return i * 2 + 1;
            }
            getRightIndex(i) {
                return i * 2 + 2;
            }
            // 上移操作
            shiftUp(index) {
                if (index == 0) { return; } // 如果已经是根节点，就不用再上移了
                const parentIndex = this.getParentIndex(index);
                if (this.heap[parentIndex] && this.heap[parentIndex].val > this.heap[index].val) {
                    this.swap(parentIndex, index);
                    this.shiftUp(parentIndex)
                }
            }
            // 下移操作
            shiftDown(index) {
                const leftIndex = this.getLeftIndex(index);
                const rightIndex = this.getRightIndex(index);
                if (this.heap[leftIndex] && this.heap[leftIndex].val < this.heap[index].val) {
                    this.swap(leftIndex, index);
                    this.shiftDown(leftIndex);
                }
                if (this.heap[rightIndex] && this.heap[rightIndex].val < this.heap[index].val) {
                    this.swap(rightIndex, index);
                    this.shiftDown(rightIndex);
                }
            }
            // 插入
            insert(value) {
                this.heap.push(value);
                this.shiftUp(this.heap.length - 1);
            }
            // 删除堆顶
            pop() {
                if (this.size() === 1) return this.heap.shift();
                const top = this.heap[0]
                this.heap[0] = this.heap.pop();  // 删除最后一个元素并把值赋值给堆顶，就相当于堆顶和最后一个元素交换再删除它
                this.shiftDown(0);
                return top;
            }
            // 获取堆顶
            peek() {
                return this.heap[0];
            }
            // 获取堆的大小
            size() {
                return this.heap.length;
            }
        }

        /**
         * Definition for singly-linked list.
         * function ListNode(val, next) {
         *     this.val = (val===undefined ? 0 : val)
         *     this.next = (next===undefined ? null : next)
         * }
         */
        /**
         * @param {ListNode[]} lists
         * @return {ListNode}
         */
        var mergeKLists = function(lists) {
            const res = new ListNode(0); // 保存输出链表
            let p = res; // 定义一个指针指向输出链表
            const h = new MinHeap();
            lists.forEach(l => { // 遍历数组中的K个链表头，插入堆中
                if(l) h.insert(l);
            });
            while(h.size()) {
                const n = h.pop(); // 弹出堆顶
                p.next = n; // 接到输出链表后面
                p = p.next; // 指向输出链表的p指针后移
                if (n.next) h.insert(n.next); // 如果堆顶节点后面还有链表，把后面那个插入堆中
            }

            return res.next;
        };
    </script>
</body>
</html>